package jianzhi_offer;

import java.util.ArrayList;

public class _40_和为S的连续正数序列 {
    public static void main(String[] args) {
        _40_和为S的连续正数序列 test = new _40_和为S的连续正数序列();
        Object res = test.FindContinuousSequence(100);
    }

    public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        int []dp = new int[sum];
        for(int i=1;i<dp.length;++i) {
            dp[i] = dp[i - 1] + i;
        }
        for(int i=1;i<dp.length;++i){
            if(dp[i]<sum) continue;
            for(int j=i-2;j>=0;--j){
                if(dp[i]-dp[j] == sum){
                    res.add(generator(j,i));
                }else if(dp[i]-dp[j] > sum){
                    break;
                }
            }
        }
        return res;
    }

    public ArrayList<Integer> generator(int left,int right){
        ArrayList<Integer> res = new ArrayList<Integer>();
        for(int i=left+1;i<=right;++i){
            res.add(i);
        }
        return res;
    }
}
